package cn.fansunion.leecode.subArray;

/**
 * 121. 买卖股票的最佳时机 https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock
 * 
 * @author wen.lei@brgroup.com
 *
 *         2021-12-25
 */
public class BestTimeToBuyAndSellStock {

    /**
     * @param args
     */
    public static void main(String[] args) {
        // 暴力破解
        final int[] prices = new int[] {7, 1, 5, 3, 6, 9,12};
        int maxProfit = maxProfit(prices);
        System.out.println(maxProfit);
        // 先转换问题 为 求最大子序和
        int[] pricesSub = new int[prices.length - 1];
        for (int i = 0; i < prices.length - 1; i++) {
            pricesSub[i] = prices[i + 1] - prices[i];
        }
        int maxProfit2 = MaxSubArray.maxSubArray(pricesSub);
        System.out.println(maxProfit2);

    }

    /**
     * 2重for循环, 超出时间限制
     * 
     * @param prices
     * @return
     */
    public static int maxProfit(int[] prices) {
        int max = 0;
        for (int i = 0; i < prices.length - 1; i++) {
            for (int j = i + 1; j < prices.length; j++) {
                if (prices[j] - prices[i] > max) {
                    max = prices[j] - prices[i];
                }
            }
        }
        return max;
    }
}
